// // 全排列：给定一个数组[1,2,3]，需要你返回数组中元素的所有排列
// // 返回[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
// // 解题思路：最简单的使用暴力法，多层for循环遍历，但是如果不知道传递数组的长度就不好做
// // 可以使用回溯法  遍历下去，再返回 需要做标记

// const permute = (nums) => {
//   // 一次的数据　
//   const path = []
//   // 所有的结果
//   const res = []
//   // 该位置的数字之前是否访问过，默认为0表示未访问过
//   let use = new Array(nums.length).fill(0)
//   // 遍历的深度
//   let depth = 0

//   dfs(nums, depth, use, path, res)
//   return res

// }
// function dfs (nums, depth, use, path, res) {
//   // 递归退出条件，如果深度等于数组长度，则说明已经遍历到树的叶子节点
//   if (depth === nums.length) {
//     res.push([...path])
//     return
//   }
//   // 遍历数组
//   for (let i = 0; i < nums.length; i++) {
//     // 判断当前元素是否使用过，如果用过则跳出
//     if (use[i]) {
//       continue
//     }
//     path.push(nums[i])
//     depth++
//     use[i] = 1
//     dfs(nums, depth, use, path, res)
//     use[i] = 0
//     depth--
//     path.pop()
//   }

// }
// console.log(permute([1, 2, 3]))



// 全排列：给定一个数组[1,2,3]，需要你返回数组中元素的所有排列
// 返回[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
// 解题思路：最简单的使用暴力法，多层for循环遍历，但是如果不知道传递数组的长度就不好做
// 可以使用回溯法  遍历下去，再返回 需要做标记

const permute = (str) => {
  // 所有的结果
  const nums = str.split('')
  const res = []
  // 一次的数据，这里需要的返回形式是['ab','ba']的类型，因此每一次的遍历结果可用字符串保存
  let path = ''
  // 该位置的数字之前是否访问过，默认为0表示未访问过
  let use = new Array(nums.length).fill(0)
  // 遍历的深度
  let depth = 0
  const dfs = () => {
    // 递归退出条件，如果深度等于数组长度，则说明已经遍历到树的叶子节点
    if (depth === nums.length) {
      res.push(path)
      return
    }
    // 遍历数组
    for (let i = 0; i < nums.length; i++) {
      // 判断当前元素是否使用过，如果用过则跳出
      if (use[i]) {
        continue
      }
      // 字符串拼接
      path += nums[i]
      // 深度++
      depth++
      // 标志当前数据已使用过
      use[i] =
        // 递归调用
        dfs()
      // 开始回溯
      use[i] = 0
      depth--
      // 字符串删除最后一个
      path = path.substring(0, path.length - 1)
    }
  }
  dfs()
  return res
}
console.log(permute('abc'))